Autoévaluation

Par définition, nous avons que $ 1 !=1$, $ 2 ! = 1\times 2 = 2$, $ 3 ! = 1\times 2\times 3 = 6$, $ 4 ! = 1\times 2\times 3 \times 4= 24$. La factorielle $ 100 !$ est plus difficile. Cependant, il n’est pas nécessaire de le faire à la main. Par exemple, la plupart des chiffriers (par exemple Excel) ont une fonction pour calculer la factorielle (par ex. FACT).

9332621544394415268169923885626670049071596826438162146859
2963895217599993229915608941463976156518286253697920827223
758251185210916864000000000000000000000000

Pour en savoir plus :

On peut aussi faire le calcul avec la formule de Stirling.

On peut aussi le faire avec un langage informatique comme Python :

Il suffit de calculer $ \frac{n !}{k ! (n-k) !}$. On obtient $ \frac{10 !}{1 ! (10-1) !}=10$, $ \frac{10 !}{2 ! (10-2) !}=45$, $ \frac{10 !}{3 ! (10-3) !}=120$, et $ \frac{10 !}{4 ! (10-4) !}=210$.

Nous avons que $ \sum_{k=1}^4 {n \choose k} k = 10 \times 1+ 45 \times2 + 120 \times 3+ 210\times 4=1300$.

On peut aussi le faire avec un langage informatique comme Python :

On applique simplement un algorithme glouton. Comme tous les pays ont une valeur égale à nos yeux, il suffit de trier les pays par ordre inverse de leur espace de stockage :

– Sénégal (0,2 Mo)
– Brésil (0,3 Mo)
– Grande-Bretagne (0,4 Mo)
– Italie (0,4 Mo)
– France (0,5 Mo)
– Canada (0,8 Mo)
– Allemagne (1,3 Mo)
– États-Unis (1,4 Mo)

Ensuite, on constate que l’on peut stocker les pays suivants :

– Sénégal (0,2 Mo)
– Brésil (0,3 Mo)
– Grande-Bretagne (0,4 Mo)
– Italie (0,4 Mo)
– France (0,5 Mo)
– Canada (0,8 Mo)

L’algorithme glouton cesse son travail avec l’Allemagne.

On doit commencer par faire un group by sur l’échantillon. Sélectionnons d’abord les colonnes qui nous intéressent :

produit	pays
crayon	Canada
livre	France
vélo	Canada
livre	Allemagne
crayon	France
vélo	Canada
crayon	Canada
livre	France
vélo	Canada
crayon	Canada
crayon	Canada

Regroupons les valeurs semblables :

produit	pays
crayon	Canada
crayon	Canada
crayon	Canada
crayon	Canada
vélo	Canada
vélo	Canada
vélo	Canada
livre	France
livre	France
livre	Allemagne
crayon	France

Calculons le group by :

produit	pays	décompte
crayon	Canada	4
vélo	Canada	3
livre	France	2
livre	Allemagne	1
crayon	France	1

Il y a $ F_0=5$ rangées dans ce group by. Nous savons que $ \log F_0 \approx 2.32$ [1], donc la valeur initiale de $ k$ est $ \lceil 2.32 \rceil = 3$. Nous avons $ m_{\mathrm{max}}=4$. Nous avons que $ N’=11$.

Il nous reste maintenant à exécuter la boucle suivante :

– Tant que $ F

• $ p\leftarrow (m_\textrm{max}/{N’})^{1/k}$
• $ F\leftarrow \sum_{a=0}^k {k\choose a} (1-(p^{k-a}(1-p)^a)^{N’})$ [2]
• $ k \leftarrow k+1$

Heureusement, il suffit de passer une seule fois dans la boucle après quoi nous avons $ p\approx 0.71$ et $ F=8$.

Par exemple, on peut calculer $ F$ à partir des valeurs de $ k$ et de $ N’$ en Python dans un langage informatique comme Python :

Il faut ensuite terminer le calcul avec ce qui suit la boucle dans l’algorithme. Plus précisément, il faut ensuite faire le calcul suivant :

– Posons $ p\leftarrow (m_\textrm{max}/N)^{1/k}$
– Valeur retournée : $ \sum_{a=0}^k {k\choose a} (1-(p^{k-a}(1-p)^a)^N)$

La valeur retournée est 16. On s’attend donc à ce qu’il n’y ait que 16 rangées dans le group by effectué sur l’ensemble de la table.

Le OU logique est tel que la valeur 1 est plus probable comme résultat que la valeur 0. Prenons le cas où les fonctions de hachage ne génèrent qu’un seul bit. Alors, la valeur hachée combinée de 0 se produira avec une probabilité de $ \frac{1}{2}\frac{1}{2}=\frac{1}{4}$ alors que la valeur 1 se produira avec la probabilité $ \frac{3}{4}$. Cette fonction de hachage n’est donc pas uniforme, et donc, elle n’est pas indépendante trois-à-trois.

La même analyse peut se faire avec le ET logique, sauf que, cette fois-ci, c’est la valeur 0 qui est plus probable.

On commence par remplacer les valeurs par les valeurs hachées :

colonne 1	colonne 2	OU exclusif	position bit 1
000	011	011	2
000	101	101	1
010	101	111	1
000	011	011	2
010	111	101	1
000	111	111	1
110	011	101	1

Le bit 1 le plus à droite est à la position 2. L’estimation est donc $ 2^2/0.77351 \approx 5.17$. La valeur exacte est 6.

[1] Attention ! Toujours prendre le logarithme en base 2.

[2] La valeur $ {k\choose a}$ est le coefficient binomial.